Scalable distributed databases have been proposed along with an increase in the number of pieces of data. Most of the scalable databases realize scalability by supporting only a simple inquiry process such as only a one-dimensional range search. On the other hand, scalable databases enabling a multidimensional-range search by mapping a multidimensional value to a one-dimensional value have also been proposed (Non-Patent Document 1 mentioned below). In Non-Patent Document 1 mentioned below, a multidimensional-range search for one-dimensional data is generally realized as follows.
There exists an indexing unit and a data storage unit. A data set is divided into pages so as to be set to be equal to or less than a certain number of threshold values, and is stored in the data storage unit. At this time, the data set is spatially divided by a space-based space division method so that the number of pieces of data included in each partial space becomes equal to or less than a threshold value, and the divided data sets are distributed to pages associated with the respective partial spaces.
FIG. 7 is a diagram illustrating an example of the space division of a two-dimensional space mapped to a data set. In FIG. 7, the two-dimensional space is represented in a one-dimensional manner using a space-filling curve called Z-curve, and a one-dimensional key value is represented by binary numbers. In the indexing unit, each partial space is given a name on the basis of the longest common prefix of a bit string of a key value included in each partial space, and a sequence of the partial spaces sorted by names is an index. FIG. 8 is a diagram illustrating an index generated from the example of FIG. 7.
In Non-Patent Document 1 mentioned below, the multidimensional-range search is realized by operating the indexing unit as follows. Among sections obtained by representing a search target range (search space) in a one-dimensional manner, a bit string indicating a maximum value (referred to as a maximum point) and a bit string indicating a minimum value (referred to as a minimum point) are acquired. At this time, suppose that the search space is a region indicated by a dotted line in FIG. 9. In this case, a minimum point is a position “000011” at the lower left corner in the region, and a maximum point is a position “100111” at the upper right corner in the region. Subsequently, in the method, a range from the minimum point to the maximum point is scanned on the index. At this time, it is checked whether or not at least a portion of each of the partial spaces within the scanning range overlaps a range to be searched for, and a data page associated with the overlapping partial space is determined to be an object to be searched for. According to the example of FIG. 9, a range from a space name “0000**” to a space name “10****” is checked. That is, in this example, the overlapping of the search space and each of partial spaces corresponding to substantially all entries on the index is checked. However, the partial spaces overlapping the search space are only four partial spaces of “0000**”, “0001**”, “001***”, and “10****”. As a result of the checking, a plurality of partial spaces of “010000” to “011111” does not overlap the search space and are excluded from objects to be searched for.